package com.bee.剑指offer;

import java.util.HashSet;
import java.util.Set;

/**
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 * <p>
 * 第一种解法：就是使用set，map尽心集合的去重
 * <p>
 * 方法二：快慢指针，需要思考为什么在向遇出，相遇的位置到环节点，和头节点到环节点的位置距离相同
 *
 * @author yong
 * @date 2021-10-27
 */
public class 链表中环的入口结点 {

    /**
     * 集合实现，用这个，简单，快慢指针时间复杂度也是n
     */
    public static ListNode EntryNodeOfLoop(ListNode pHead) {
        Set<ListNode> contain = new HashSet<>();
        while (pHead != null) {
            if (contain.contains(pHead)) {
                return pHead;
            }
            contain.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }

    /**
     * 快慢指针思想
     */
    public static ListNode EntryNodeOfLoop2(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // fast == slow节点相遇
            if (slow == fast) {
                break;
            }
        }
        // 无环
        if (fast == null || fast.next == null) {
            return null;
        }
        ListNode cur = pHead;
        while (cur != slow) {
            cur = cur.next;
            slow = slow.next;
        }
        return cur;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next;
        ListNode listNode = EntryNodeOfLoop2(head);
        System.out.println(listNode.val);
    }
}

class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
